#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {
        sort(e.begin(), e.end(), [&e](const vector<int>& v1, const vector<int>& v2)
            {
                return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
            });

        vector<int> ret;
        int n = e.size();
        ret.push_back(e[0][1]);

        for (int i = 1; i < n; ++i)
        {
            if (e[i][1] > ret.back())
            {
                ret.push_back(e[i][1]);
            }
            else
            {
                int b = e[i][1];
                int left = 0;
                int right = ret.size() - 1;
                int mid = 0;
                while (left < right)
                {
                    mid = left + (right - left) / 2;
                    if (ret[mid] >= b)
                    {
                        right = mid;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }

                if (ret[left] > b)
                    ret[left] = b;
            }
        }

        return ret.size();
    }
};